package com.whcoding.test.common;


import java.util.Arrays;

/**
 * @program: spring-boot-learning
 * @description: 8大排序法
 * <p>
 * https://blog.csdn.net/qq_43414012/article/details/114841453
 * https://blog.csdn.net/CSDN_handsome/article/details/109055036
 * 冒泡排序  快速排序  【交换排序】
 * <p>
 * 直接插入排序 希尔排序 【插入排序】
 * 简单选择排序 堆排序  【选择排序】
 * 归并排序
 * 基数排序
 * @author: whcoding
 * @create: 2022-04-01 18:29
 **/
public class SuanFaSort {

	/**
	 * 1.冒泡排序法
	 */
	public void bubblingSort() {

		int[] arrInts = {1, 36, 55, 8, 6, 9, 15, 88, 22, 19, 5, 3};
		System.out.println(Arrays.toString(arrInts));
		int temp = 0;

		//外层循环 判断需要走多少次
		for (int i = 0; i < arrInts.length; i++) {
			for (int j = 0; j < arrInts.length - 1 - i; j++) {
				//从大到小排序
				//将> 改为<则为从小到大排序
				if (arrInts[j + 1] > arrInts[j]) {
					temp = arrInts[j];
					arrInts[j] = arrInts[j + 1];
					arrInts[j + 1] = temp;
				}
			}
		}
		System.out.println("冒泡排序方法一:" + Arrays.toString(arrInts));
		boolean flag = false;
		//外层循环 判断需要走多少次 优化
		for (int i = 0; i < arrInts.length; i++) {

			for (int j = 0; j < arrInts.length - 1 - i; j++) {
				//从大到小排序
				//将> 改为<则为从小到大排序
				if (arrInts[j + 1] > arrInts[j]) {
					temp = arrInts[j];
					arrInts[j] = arrInts[j + 1];
					arrInts[j + 1] = temp;
					flag = true;
				}
			}
			if (flag) {
				break;
			}
		}
		System.out.println("冒泡排序方法二:" + Arrays.toString(arrInts));
	}

	/**
	 * 冒泡排序2
	 *
	 * @param a
	 */
	public static void bubblingSort2(int[] a) {
		//外层循环控制比较的次数
		for (int i = 0; i < a.length - 1; i++) {
			//内层循环控制到达位置
			for (int j = 0; j < a.length - i - 1; j++) {
				//前面的元素比后面大就交换
				if (a[j] > a[j + 1]) {
					int temp = a[j];
					a[j] = a[j + 1];
					a[j + 1] = temp;
				}
			}
		}
	}

	/**
	 * 2.快速排序
	 */
	public static void quickSort(int[] a, int low, int high) {
		//已经排完
		if (low >= high) {
			return;
		}
		int left = low;
		int right = high;

		//保存基准值
		int pivot = a[left];
		while (left < right) {
			//从后向前找到比基准小的元素
			while (left < right && a[right] >= pivot)
				right--;
			a[left] = a[right];
			//从前往后找到比基准大的元素
			while (left < right && a[left] <= pivot)
				left++;
			a[right] = a[left];
		}
		// 放置基准值，准备分治递归快排
		a[left] = pivot;
		quickSort(a, low, left - 1);
		quickSort(a, left + 1, high);
	}


	/**
	 * 3.直接插入排序
	 * 通过交换进行插入排序，借鉴冒泡排序
	 */
	public static void insertSort(int[] a) {
		for (int i = 0; i < a.length - 1; i++) {
			for (int j = i + 1; j > 0; j--) {
				if (a[j] < a[j - 1]) {
					int temp = a[j];
					a[j] = a[j - 1];
					a[j - 1] = temp;
				}
			}
		}
	}

	/**
	 * 通过将较大的元素都向右移动而不总是交换两个元素
	 * 插入排序二
	 *
	 * @param a
	 */
	public static void insertSort2(int[] a) {
		for (int i = 1; i < a.length; i++) {
			int num = a[i];
			int j;
			for (j = i; j > 0 && num < a[j - 1]; j--) {
				a[j] = a[j - 1];
			}
			a[j] = num;
		}
	}

	/**
	 * 4.希尔排序
	 */
	public void xierSort1(int[] a) {
		int length = a.length;
		int h = 1;
		while (h < length / 3) h = 3 * h + 1;
		for (; h >= 1; h /= 3) {
			for (int i = 0; i < a.length - h; i += h) {
				for (int j = i + h; j > 0; j -= h) {
					if (a[j] < a[j - h]) {
						int temp = a[j];
						a[j] = a[j - h];
						a[j - h] = temp;
					}
				}
			}
		}
	}

	/**
	 * 5.简单选择排序
	 *
	 * @param a
	 */
	public void choiceSort(int[] a) {
		for (int i = 0; i < a.length; i++) {
			int min = i;
			//选出之后待排序中值最小的位置
			for (int j = i + 1; j < a.length; j++) {
				if (a[j] < a[min]) {
					min = j;
				}
			}
			//最小值不等于当前值时进行交换
			if (min != i) {
				int temp = a[i];
				a[i] = a[min];
				a[min] = temp;
			}
		}
	}

	/**
	 * 6.堆排序
	 */
	public void heapSort(int[] a) {
		for (int i = a.length - 1; i > 0; i--) {
			max_heapify(a, i);
			//堆顶元素(第一个元素)与Kn交换
			int temp = a[0];
			a[0] = a[i];
			a[i] = temp;
		}
	}

	/***
	 *
	 *  将数组堆化
	 *  i = 第一个非叶子节点。
	 *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
	 *  叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
	 *
	 * @param a
	 * @param n
	 */
	public static void max_heapify(int[] a, int n) {
		int child;
		for (int i = (n - 1) / 2; i >= 0; i--) {
			//左子节点位置
			child = 2 * i + 1;
			//右子节点存在且大于左子节点，child变成右子节点
			if (child != n && a[child] < a[child + 1]) {
				child++;
			}
			//交换父节点与左右子节点中的最大值
			if (a[i] < a[child]) {
				int temp = a[i];
				a[i] = a[child];
				a[child] = temp;
			}
		}
	}


	/**
	 * 合并数组
	 */
	public static void merge(int[] arr, int low, int middle, int high) {
		// 用于存储归并后的临时数组
		int[] temp = new int[high - low + 1];
		// 记录第一个数组中需要遍历的下标
		int i = low;
		// 记录第二个数组中需要遍历的下标
		int j = middle + 1;
		// 记录在临时数组中存放的下标
		int index = 0;
		// 遍历两个数组，取出小的数字，放入临时数组中
		while (i <= middle && j <= high) {
			// 第一个数组的数据更小
			if (arr[i] <= arr[j]) {
				// 把更小的数据放入临时数组中
				temp[index] = arr[i];
				// 下标向后移动一位
				i++;
			} else {
				temp[index] = arr[j];
				j++;
			}
			index++;
		}
		// 处理剩余未比较的数据
		while (i <= middle) {
			temp[index] = arr[i];
			i++;
			index++;
		}
		while (j <= high) {
			temp[index] = arr[j];
			j++;
			index++;
		}
		// 把临时数组中的数据重新放入原数组
		for (int k = 0; k < temp.length; k++) {
			arr[k + low] = temp[k];
		}
	}

	/**
	 * 7.归并排序
	 */
	public static void mergeSort(int[] arr, int low, int high) {
		int middle = (high + low) / 2;
		if (low < high) {
			// 处理左边数组
			mergeSort(arr, low, middle);
			// 处理右边数组
			mergeSort(arr, middle + 1, high);
			// 归并
			merge(arr, low, middle, high);
		}
	}


	/**
	 * 8.基数排序
	 */
	public static void radixSort(int[] arr) {
		// 存放数组中的最大数字
		int max = Integer.MIN_VALUE;
		for (int value : arr) {
			if (value > max) {
				max = value;
			}
		}
		// 计算最大数字是几位数
		int maxLength = (max + "").length();
		// 用于临时存储数据
		int[][] temp = new int[10][arr.length];
		// 用于记录在 temp 中相应的下标存放数字的数量
		int[] counts = new int[10];
		// 根据最大长度的数决定比较次数
		for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
			// 每一个数字分别计算余数
			for (int j = 0; j < arr.length; j++) {
				// 计算余数
				int remainder = arr[j] / n % 10;
				// 把当前遍历的数据放到指定的数组中
				temp[remainder][counts[remainder]] = arr[j];
				// 记录数量
				counts[remainder]++;
			}
			// 记录取的元素需要放的位置
			int index = 0;
			// 把数字取出来
			for (int k = 0; k < counts.length; k++) {
				// 记录数量的数组中当前余数记录的数量不为 0
				if (counts[k] != 0) {
					// 循环取出元素
					for (int l = 0; l < counts[k]; l++) {
						arr[index] = temp[k][l];
						// 记录下一个位置
						index++;
					}
					// 把数量置空
					counts[k] = 0;
				}
			}
		}
	}


}
